// 链表的逆序   // 递归
function reverseList(head) {
    if (!head || !head.next) return head;
    var next = head.next;
    var revertHead = reverseList(head.next)
    next.next = head
    head.next = null;
    return revertHead
}

function ListNode(val) {
    this.val = val;
    this.next = null;
}

// 从第n位开始 逆序
function reverseList(head, m, n) {
    let dummy = new ListNode(0);
    dummy.next = head;

    let temHead = dummy;
    // 找到起始位置
    for (let i = 0; i < m - 1; i++) {
        temHead = temHead.next
    }

    var pre = null;
    var curr = temHead.next;
    for (let j = 0; j <= n - m; j++) {
        var next = curr.next
        temHead.next = pre;
        pre = curr;
        curr = next;
    }

    temHead.next.next = curr
    temHead.next = pre
    return dummy.next
}

// 判断链表求交点
function getIntersectionNode(headA, headB) {
    while (headA) {
        headA.tag = true;
        headA = headA.next
    }
    while (headB) {
        if (headB.tag) return true;
        headB = headB.next
    }
    return null
}

// 判断链表是否有环
function hasCycle(head) {
    while (head) {
        if (head.tag) return true
        headA.tag = true;
        headA = headA.next
    }
    return false
}



// 链表的划分
// 第几个之前全部小于x 后面的大于x
function ListNode(value){
    this.value = value;
    this.next = null;
}
// 方法1，大于的放在一个数组里 再循环补在后面
var partition = function(head,x){
    let node = new ListNode();
    node.next = head;
    let prev = node;
    let cur = node.next;
    let arr = [];
    let isHas = 0;

    while(cur){
        if(cur.val == x || cur.val > x){
            prev.next = cur.next
            cur.next = null
            arr.push(cur)
            isHas = 1
        }
        if(isHas){
            cur = prev.next;
            isHas = 0
        }else {
            prev = prev.next
            cur = cur.next
        }
    }

    while(arr.length){
        prev.next = arr.shift();
        prev = prev.next
    }
    return node.next
}

// 两个链表 ，然后拼接
var partition = function(head, x) {
    let before = new ListNode(0)
    let after = new ListNode(0)
    let aindex = after
    let bindex = before
    while(head){
        let node = new ListNode(head.val)
        if(head.val > x || head.val == x){
            aindex.next = node
            aindex = aindex.next
        }else{
            bindex.next = node
            bindex = bindex.next
        }
        head = head.next
    }
    bindex.next = after.next
    return before.next
};

// 两个排序链表的归并
var mergeTwoList = function(l1,l2){
    if(l1 === null){
        return l2
    }
    if(l2 === null){
        return l1
    }
    if(l1.val < l2.val){
        l1.next = mergeTwoList(l1.next,l2)
        return l1
    }else {
        l2.next = mergeTwoList(l1,l2.next)
        return l2
    }
}




// k个排序链表的归并 hard 放弃
// 复杂链表的复制 hard 放弃